from collections import defaultdict
from typing import List

# 1.我们维护两个滑动窗口，一个用于找到子数组的 最大起始位置，另一个用于找到 最小起始位置，从而统计以当前右边界为结尾的子数组数量。
# 2.定义两个指针 left1 和 left2 分别表示：
# left1：子数组的和小于等于 goal 的最小起始位置。
# left2：子数组的和小于 goal 的最大起始位置。
# 3.遍历数组，用一个变量 sum_ 记录当前窗口的和：
# 扩展窗口：将当前元素加入到窗口中，增加 sum_。
# 收缩窗口：当 sum_ > goal 时，移动 left1 和 left2，同时减小 sum_。
# 计算答案：当前窗口 [left1, right] 到 [left2, right] 的子数组均满足条件。

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        left1 = left2 = 0  # 定义两个左边界
        sum1 = sum2 = 0  # 两个窗口的当前和
        result = 0  # 满足条件的子数组个数

        for right, num in enumerate(nums):
            # 扩展两个窗口
            sum1 += num
            sum2 += num

            # 收缩第一个窗口，使得 sum1 <= goal
            while left1 <= right and sum1 > goal:
                sum1 -= nums[left1]
                left1 += 1

            # 收缩第二个窗口，使得 sum2 < goal
            while left2 <= right and sum2 >= goal:
                sum2 -= nums[left2]
                left2 += 1

            # 满足条件的子数组个数
            result += left2 - left1

        return result
